import java.util.ArrayList;

public class RestoreIpAddresses {
    // 数字字符串转化为IP地址
    // https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

    ArrayList<String> ret;
    StringBuilder path;
    int count = 0;
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(s, 0);
        return ret;
    }

    private void dfs(String s, int start) {
        if (start >= s.length()) {
            if (count == 4) {
                ret.add(path.substring(0, path.length()-1));
            }
            return;
        }
        for (int i = start; i < start + 3 && i < s.length(); i++) {
            String num = s.substring(start, i+1);
            if (isValid(num)) {
                path.append(num + ".");
                count++;
                dfs(s, i+1);
                path.delete(path.length() - num.length() - 1, path.length());
                count--;
            }
        }
    }

    private boolean isValid(String s) {
        if (s.charAt(0) == '0' && s.length() > 1) {
            return false;
        }
        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }
}
